package doing;

import org.junit.Test;

import static com.study.util.LogUtil.info;
import static com.study.util.SwapUtil.swap;

/**
 * 516. Longest Palindromic Subsequence 最长回文子序列
 * <p>
 * 给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
 * <p>
 * 示例 1:
 * 输入: "bbbab"
 * 输出: 4
 * 一个可能的最长回文子序列为 "bbbb"。
 * <p>
 * 示例 2:
 * 输入: "cbbd"
 * 输出: 2
 * 一个可能的最长回文子序列为 "bb"。
 * <p>
 * 2019-06-13 19:13
 **/
@SuppressWarnings("all")
public class LongestPalindromicSubsequence {

    public int longestPalindromeSubseq(String s) {
        char[] chars = s.toCharArray();
        int length = s.length();
        int[] cur = new int[length];
        int[] pre = new int[length];

        for (int i = length - 1; i >= 0; i--) {
            cur[i] = 1;
            for (int j = i + 1; j < length; j++) {
                if (chars[i] == chars[j]) {
                    cur[j] = pre[j - 1] + 2;
                } else {
                    cur[j] = Math.max(cur[j - 1], pre[j]);
                }
            }
            swap(pre, cur);
        }
        return pre[length - 1];
    }

    @Test
    public void test() {
        info(longestPalindromeSubseq("bbbab"));
    }
}